// HeapPag.h: interface for the HeapPag class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_HEAPPAG_H__2FA32401_0A4C_11D4_BC5C_EFDE26819337__INCLUDED_)
#define AFX_HEAPPAG_H__2FA32401_0A4C_11D4_BC5C_EFDE26819337__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include "Type.h"
#include "NodARBB.h"

typedef unsigned TInd, TCrs, TPag;

//EMAI - inseamna Eroare de memorie sau argument invalid

/* Decomentati macroul urmator daca vreti sa monitorizati corecta utilizare a
	heapului. In acest caz functiile din heap returneaza valori de esec
	( NULL, FALSE, depinde de semnificatie ) daca argumentele au valori
	nepermise.
*/
//#define CHECK_ERROR

// Numarul maxim de intrari in heap
#define HMAX_ENTRIES ( ( unsigned )( 0x10000 / sizeof ( TNodZona ) ) )

/* Constituie un suport puternic pentru obiectele Paginrs.
	Este foarte constienta de notiunea de "pagina". Desi lucrul acesta nu pare
	natural, totusi, pentru viteza si pentru claritate e bine asa. Altfel,
	obiectele PaginaCrs ar fi trebuit sa apeleze des niste operatori "idioti"
	ce puteau opera numai cu notiunea de "lista" => timp pierdut, aglomeratie.
	Este derivata din clasa Heap.
*/

class ARBBDLL_API HeapPag {

public:
	
	// Cate pagini de ordinul nOrd sunt disponibile pe heapul curent ?
	static unsigned NoFreeNodes ( unsigned nOrd );

	/* A se apela cand se trece la urmatorul heap din tabloul HeapTable
		Pregateste clasa PaginaCrs pentru ca obiectele viitoare sa lucreze cu
		un nou heap.
		Un obiect PaginaCrs nu poate lucra decat pe UN heap.
		Tabloul HeapPag ( marimea lui ) e gestionat de aplicatie.
	*/
	static void PrepareHeap ( unsigned = HMAX_ENTRIES );

	// returneaza indicele heapului curent, din tabloul HeapTable
	static unsigned CurrentHeap ();

private:

	/* Variabila pentru contorizarea heapurilor ce se aloca de catre aplicatie
		pentru ca viitori arbori de tip CRS sa stie cu ce heap lucreaza.
		E posibil sa existe 65535 heapuri.
	*/
	static unsigned heap_counter;

	/* Constructorul primeste ca argument capacitatea heapulul ( nEntries ),
		ca numar de articole de tip "TInf", ce TREBUIE sa fie majorat de
		HMAX_ENTRIES, si creeaza heapul.
	*/
	HeapPag ( unsigned = HMAX_ENTRIES );

	// Destructorul dealoca heapul
	~HeapPag();

	typedef struct tagNodZona {
		typedef struct tagTInf {
			TCheie cheie;
			TPag pag;
		} TInf;
		TInf inf;
		TCrs urm;
	} TNodZona;

	TNodZona
		// heapul propriu zis
		* pZona;
	TCrs
		// lista nodurilor libere
		pDisp;
	TInd
		// numarul de noduri disponibile
		nDisp,
		// numarul total de noduri din heap
		nSize;
	
	const HeapPag
		// Pointer la un obiect HeapPag, utilizat ca sursa la copiere.
		* src;

	unsigned
		// Cate obiecte PaginaCrs folosesc acest heap; daca e zero se poate dealoca
		nUsing;

	/* Copiaza pagina iPag din heapul src in cel pentru care se apeleaza.
		Returneaza noua lista alocata daca copierea s-a sfarsit cu succes,
		NULL daca EMAI. Nodurile NodARBB se cloneaza.
	*/
	TPag CopyPage ( TPag iPag );

	/* Metoda de alocare a unei liste in heap; returneaza NULL daca nu mai este
		loc	pe heap. Altfel, aloca o lista de "nNr" noduri, care are la coada
		atasata lista corespunzatoare argumentului "coada". Valoarea returnata
		este cursorul listei nou create.
	*/
	TCrs alloclist ( TInd nNr = 1, TCrs coada = NULL );

	/* Metoda de dealocare a unei liste in heap; returneaza TRUE daca operatia
		s-a terminat cu succes; altfel FALSE, si in acest caz e mare bai.
		Argumentul "cap" indica lista care trebuie dealocata.
	*/
	BOOL freelist ( TCrs cap ); //atentie cu asta
	
	/* Functie de uz general, ce returneaza cursorul ultimului element din
		lista primita ca argument ( "cLista" ).
	*/
	TCrs LastNode ( TCrs cLista ) const;

	/* Returneaza inidicatorul ( cursorul ) urmatorului element inlantuit dupa
		cel indicat prin argument "cNod".
	*/
	TCrs Next ( TCrs cNod ) const;

	/* Creeaza o pagina de 1 nod, anume cel din argumentul pNod, atribuind ca
		subpagini cursorii din argumente, cLeft	respectiv cRight.
		Returneaza NULL daca ceva nu e OK -> eroare memorie sau argumente
		invalide ( EM sau AI ).
	*/
	TCrs _cdecl NewPage1 ( NodARBB* pNod, TPag iLeft = NULL, TPag iRight = NULL );

	/* Insereaza un nod de elemente { pNod, iPag }, imediat dupa nodul cNod
		Returneaza FALSE daca EMAI.
	*/
	BOOL _cdecl InsertNode ( TCrs cNod, NodARBB* pNod, TPag iPag = NULL );

	/* Scoate dintr-o lista nodul de dupa cNod, returnand pointerul la nodul
		continut. Daca EMAI, returneaza NULL.
	*/
	NodARBB* ExtractNode ( TCrs cNod );

	/* Elibereaza lista asociata unei pagini identificata de argumentul iPag,
		fara a face si stergerea obiectelor	NodARBB din pagina. Returneaza
		acelasi lucru ca Heap :: freelist.
	*/
	BOOL FreePage ( TPag iPag );

	/* Operatori de incrementare/decrementare dimensiune pagina, primita ca
		argument prin iPag.
		Returneaza valoarea actualizata a dimensiunii paginii, sau -1 daca AI.
		Se apeleaza dupa ce s-au facut insertii/extrageri de noduri in pagina.
	*/
	unsigned IncSize ( TPag iPag ) const;
	unsigned DecSize ( TPag iPag ) const;

	// Returneaza dimensiunea paginii argument iPag, sau -1 daca AI.
	unsigned Size ( TPag iPag ) const;

	/* Returneaza nodul continut de elementul referit prin cursorul iCrs, sau
		NULL daca AI.
	*/
	NodARBB* Node ( TCrs iCrs ) const;

	/* Returneaza a i-a subpagina din pagina referita prin cursorul iPag
		sau NULL daca AI.
	*/
	TPag Page ( TPag iPag, unsigned i ) const;

	/* Returneaza subpagina indicata de elementul referit prin cursorul iCrs
		sau NULL daca AI.
	*/
	TPag Page ( TCrs iCrs ) const;

	/* Functie complexa de divizare pagina, la cresterea dimensiunii acesteia
		astfel incat incalca definitia arborelui B.
		Argumente:
			iPag -> pagina in cauza;
			rpNod -> referinta la un pointer la NodARBB, care va contine
						 noul nod care urca spre parinte. Prin rpNod se intoarce
						 practic noul nod.
		Returneaza pagina din dreapta care apare in urma divizarii; pagina din
		stanga ramane indicata prin cursorul iPag. Daca AI, returneaza NULL.
	*/
	TCrs SplitPage ( TPag iPag , NodARBB*& rpNod ) const;

	/* Functie complexa de fuzionare de pagini, la scaderea dimensiunii uneia
		dintre subpagini, care poate fi cea referita de cNod sau de succesorul
		lui cNod. Una din pagini dispare; cursorul ei se returneaza. Daca EMAI
		returneaza NULL.
	*/
	TPag MergePages ( TCrs cNod );

	/* ele doua functii implementeaza operatiile de imprumut DIN stanga,
		respectiv dreapta, IN dreapta, respectiv stanga a acelui nod. Aceasta
		deplasare nu duce la modificarea ordinii nodurilor in arbore. NotiuNULLe
		de stanga/dreapta se refera la nodul referit de succesorul lui cNod.
		Se returneaza FALSE daca AI; altfel TRUE.
	*/
	BOOL LeftBorrow ( TCrs cNod ) const;
	BOOL RightBorrow ( TCrs cNod ) const;

	/* Aceste functii returneaza cel mai din dreapta, respectiv stanga element
		al subarborelui referit de argumentul iCrs. Valoarea returnata este
		pointerul la elementul extrem, sau NULL in daca AI.
	*/
	NodARBB* RightMost ( TPag iCrs ) const;
	NodARBB* LeftMost ( TPag iCrs ) const;

	/* Procedura urmatoare permite actualizarea nodului referit de cursorul
		iCrs. Argumentul pNod este noul pointer care va inlocui pe cel vechi.
		Se returneaza FALSE daca AI; altfel TRUE.
	*/
	BOOL UpdateNode ( TCrs iCrs, NodARBB* pNod ) const;
	
	friend class PaginaCrs;

};

/* Mai este definit un tablou de heapuri: HeapPag** HeapTable;
	A se declara "extern" in aplicatie, care e responsabila de alocari.
*/

#endif // !defined(AFX_HEAPPAG_H__2FA32401_0A4C_11D4_BC5C_EFDE26819337__INCLUDED_)
